COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.REQUIRE "LSP.PUB[LSP,CLT]" source_file
C00003 00003	.hd206 FALL 1977
C00008 00004	#. Knot representation.
C00018 00005
C00019 ENDMK
C⊗;
.REQUIRE "LSP.PUB[LSP,CLT]" source_file;
.PAGE FRAME 54 HIGH 80 WIDE;
.evenleftborder ← oddleftborder ← 1000;
.area text lines 3 to 54;
.area heading lines 1 to 2;
.place text;
.FONT D "GRFX35";
.
.MACRO  hd206 (TERM) ⊂
.BEGIN    NOFILL  TURNON "←→"
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY
.SKIP  
CS206  ←COMPUTING WITH SYMBOLIC EXPRESSIONS  →TERM
.TURNOFF
.END ⊃
.
.
.MACRO hw (NUMBER, DUEDATE) ⊂
.   BEGIN TURNON "←"  NOFILL
←PROBLEM SET  NUMBER
←Due  DUEDATE
.   TURNOFF END ⊃
.
.itemmac 1
.
.PORTION MAINPORTION
.PAGE ← 1
.hd206 FALL 1977
.cb TERM PROJECTS

	Term projects will be due on the day of the final exam.  
This is your chance to write and document a substantial LISP program or
to formalize and write a computer checkable proof of the correctness 
(or some other property) of a moderate sized LISP program.  
It is possible to get some flavor of B, but not A without doing a term project.
A C project will not help you to get a B.  The write up is the main part that
will be graded, so make it clear what you have done and why it works.  
Listed below are some ideas for possible term projects.  You may choose one
of these or propose your own idea.  Most of these ideas will need further
specification and delineation to make a viable project.
.BEGIN NOFILL

#. Improve the LCOM4 compiler.  Some possibilities are:

     Modify LCOM4 so that it can

	##. compile  ⊗label. 
	##. handle the %3prog%1 and related features.
	##. handle functions as arguments (as for ⊗mapcar) .
	##. recognize iteration and compile it with loops.
	##. produce more efficient arithmetic code.
	##. generate more efficient code in other cases where you might have noticed inefficiencies. 

    or invent some syntactic sugar for LISP such as "while's" or "do's and

	##. add code to LCOM4 to compile these additional constructs.


#. Write a program to play a game.  Some suggested games are

	##. 3-dimensional Tic Tac Toe
	##. Solitare
	##. Nim 
	##. Hackenbush
.END

    Be sure to hold individual test runs to a few seconds.  It is easy to
use large amounts of computer time in such projects.  


#. Transformations, rules, derivations, checking.

	Consider the general situation of a data set, a relation on the set
and a set of rules defining transformations on the set which either
preserve the relation, or given a member of the set produce a related member.
Then some interesting problems are 
.BEGIN NOFILL

	##. To represent the data as S-expressions.
	##. To write LISP functions which carry out the transformations.
	##. State and prove the correctness of these functions.
	##. Write a system to use these functions to convert a given element into some desired form.
	##. Write a system using these functions to check "derivations"  according to the rules.

(3.4 is not always possible, since some of these problems may involve undecidable questions.)

    Some possible data and rules are

	##. Trigonometric expressions and identities.
	##. Some class of functions and rules for integrating them.
	##. Boolean expressions and the rules for manipulating them.
	##. Algebraic expressions and simplification rules.
	##. Converting conditional expressions into cannonical form. [McCarthy 1963]
	##. Knots.  [See below.]
.END
	    	
#. Proving properties of LISP functions.

	Prove the correctness or other interesting property of a moderate size
LISP function and check your proof using the proof checker FOL.   For example
Exercise_3 of Chapter_III would be suitable.  Or you may write your own fucntion
and specifications.

#. Graphs.

	Write a program to determine the symmetry group of a graph.

#. Knot representation.

	A knot can be repsented as a graph with edges labeled by the symbols in the 
set {+,-}.
The algorithm for doing this is as follows.  Draw the knot (with crossovers if
necessary) in the plane.  The plane is thus divided into regions.  Classify a region
even or odd according to whether an even or odd number of lines must be crossed
in order to get to the outermost region.  (Note that the outermost region is even 
and all of its neighbors are odd.  Also note that if the number of lines crossed
by one route is even then that will be the case for any route.  Same for odd.)
Now form a graph with one vertex for each odd region.  Draw one line between
vertices a and b for each crossover point at which regions a and b are tangent.  
(The graph may have multiple edges or loops.)  There are essentially two
possibilities  for four regions a, b, c, d meeting at a crossover where a and b are
the odd pair.  These are shown in figure 1.  (We assume that the knot has been 
drawn without degenerate crossover points and other bad things.)
.SKIP 2
.BEGIN SELECT D; 
.NOFILL
.PREFACE 0
.MILLPREFACE ← 0
.TURNOFF "α"
.TURNON "∂"
.n1←20 ; n2←40; n3←60; n4←40;
.Group

∂(n1)`≥   a   ≤'	∂(n3)`≥   a   ≤'
∂(n1+2)`≥   ≤'          ∂(n3+2)`≥   ≤'
∂(n1)c   `≤'   d	∂(n3)c   `≥'   d
∂(n1+3) ≤' `≥		∂(n3+3) ≤' `≥
∂(n1+1)≤'     `≥	∂(n3+1)≤'     `≥
∂(n1)'    b    `	∂(n3)'    b    `


∂(n1+4)  (i)		∂(n3+4)  (ii)


∂(n4)Figure 1.
.apart
.end
	In case (i) the corresponding edge joining a and b
is labeled "+". In case (ii) it is labeled "-".  



	To describe the allowed transformations on a knot, think of it as
made of string.  Then any transformation to further tangle or untangle the string
is allowed as long as you do not cut the string. In Figure 2 we show some basic
transformations (based on local configurations) giving the original knot
form and the corresponding graph form.  The dual transformations
(with signs and crossovers and even/odd region parity all interchanged) are
also to be included in any application.



.BEGIN SELECT D; 
.NOFILL
.PREFACE 0
.MILLPREFACE ← 0
.TURNOFF "α"
.TURNON "∂"
.n1←20 ; n2←60;  n4←45;


.if lines < 9 then next page;
T1:∂(n1+2)`≥'				∂(n2+1)~  ~
∂(n1)a '∂(n1+2)≥ `∂(n1+4)≤ b  ∂(n4)↔	∂(n2)a~  ~b
∂(n1+2)≤'≥				∂(n2+1)~  ~


∂(n1+3) ≤α≥+	
∂(n1)a '∂(n1+2)≥   `∂(n1+6)≤ b  ∂(n4)↔	∂(n2+1)#  #
∂(n1+3) `α'+				∂(n2+1)a  b


.n1←20; n3←60; n4← 45;
.if lines < 10 then next page;
T2:∂(n1+4)  ≤αα≥
∂(n1+3) / b  \				∂(n3)αααααααααααα
∂(n1)αααααααααααα	∂(n4)↔		∂(n3+5)   b
∂(n1)a/        \c			∂(n3)αααααααααααα


∂(n1+4)  +    -				
∂(n1)a ααααα∂(n1+6)#αααα c	∂(n4)↔	∂(n3+5)   #
∂(n1+6)    b				∂(n3+5)   b



.n1←20 ; n2←60;  n4←45;
.if lines < 15 then next page;
T3:∂(n1+7)     b ≤		∂(n2)`≥~ b
∂(n1+6)    ~≤'		∂(n2+2)~≥
∂(n1+1)≥   ≤'		∂(n2+2)~ `≥
∂(n1)a `≤'d~	∂(n4)↔	∂(n2)a ~ ≤'      
∂(n1+1)≤' `≥~		∂(n2+2)≤'
∂(n1+6)    ~≥		∂(n2)≤'~ c
∂(n1+6)    ~c`≥


∂(n1+8)      b			∂(n2+5)   b
∂(n1+5)   +≤'			∂(n2+2)-≤'~
∂(n1)a ααα'∂(n1+5)≥d  ∂(n4)↔	∂(n2)a '∂(n2+2)≥  ~ +
∂(n1+1)-   +`≥			∂(n2+2)-`≥~
∂(n1+8)      c			∂(n2+5)   c



.n1←20;n2←40;n3←60;n4←45;
.if lines < 13 then next page;
T4:∂(n1+7)     ~					∂(n3+3) ~
∂(n1+1)≤α≥ ≤ααα≥				∂(n3+1)≤α~α≥ ≤α≥
∂(n1)'∂(n1)≥ a / b~  `∂(n1+10)≤  c   ∂(n4)↔	∂(n3)'∂(n3)≥ a~  /   `∂(n3+10)≤ c
∂(n1+1)`α' `α~α'				∂(n3+1)`ααα' `α'
∂(n1+7)     ~					∂(n3+3) ~


∂(n1+8)      +	
∂(n1+6)    ≤αα≥					∂(n3+2)-≤αααα≥
∂(n1)a ααα'∂(n1+5)≥b   `∂(n1+10)≤ c  ∂(n4)↔	∂(n3)a /   +≤α≥∂(n3+9)\ c
∂(n1+2)-   `αα'					∂(n3+2)\    `α'∂(n3+9)/
∂(n1+8)      +					∂(n3+2)-`αααα'



.n4←35;n5←52;
.if lines < 15 then next page
T5:∂(n1+4)  ~  c		∂(n2)`≥~   c		∂(n3+5)   ~  c
∂(n1)ααααααααα 		∂(n2+2)\      ≤		∂(n3)`≥ ≤'~`≥ ≤'
∂(n1+4)  ~     	∂(n4)↔	∂(n2)a ~`≥'`≤' 	∂(n5)↔	∂(n3)a≤`≥d~ ≤'≥
∂(n1)a   ~     		∂(n2+2)~' `' `≥		∂(n3)'   `α'   `
∂(n1)αααα~αααα 		∂(n2)≤'~   b		∂(n3+5)   ~  b
∂(n1+4)  ~  b  


∂(n1+7)     c		∂(n2+7)     c		∂(n3+7)      c
∂(n1+2)+  ≤' 		∂(n2+3) + ≤'∂(46)∩¬	∂(n3+2)+  -≤'¬
∂(n1+3) ≤'     ∂(n4)↔	∂(n2+3) ≤' ~~  	∂(n5)↔	∂(n3)a ααα'∂(n3+5)≥d ~ +
∂(n1)a  `≥   		∂(n2)a  `≥-~~ +		∂(n3+5)   -`≥∪
∂(n1+3) + `≥ 		∂(n2+3) + `≥∂(46)&∪	∂(n3+7)      b
∂(n1+7)     b		∂(n2+7)     b



.group
T6:			∂(n2+3) ≤α≥    	
			∂(n2+2)≥∂(n2+2)' d `∂(n2+6)≤	∂(n3+3) ≤α≥     
∂(n1+4)  ≤α≥    	∂(n2+3) `≥'    			∂(n3+2)/ d \  
∂(n1+3) / b \ ∂(n4)↔	∂(n2+3) /b\   	∂(n5)↔		∂(n3)αα αααααα
∂(n1)αααααααα\αα	∂(n2)αααααα αα			∂(n3+3) `≥'   
∂(n1)a/       \c	∂(n2)a/     \c			∂(n3)a ≤' `≥ c


			∂(n2+4)  d			∂(n3+5)   d
			∂(n2+3) -~			∂(n3+4)  ≤≥
∂(n1+3) +   +	∂(n4)↔	∂(n2+4)  ~b   	∂(n5)↔		∂(n3+1)-≤'  `≥-
∂(n1)a ααααααα c	∂(n2+1)+≤' `≥+	        ∂(n3+1)'∂(n3+1)αααααααα∂(n3+8)`
∂(n1+5)   b		∂(n2)a'     `c			∂(n3)a   +    c


∂(40)Figure 2.
.apart
.end


	Figure 3. shows a sample application transforming a knot into its
mirror image.  Here tn is the dual of the transformation
Tn.   Tni is the left most, and Tnii is the rightmost of the transformations Tn.
.BEGIN SELECT D; 
.NOFILL
.PREFACE 0
.MILLPREFACE ← 0
.TURNOFF "α"
.TURNON "∂"
.group


∂(22)≤ααα≥				∂(62)≤ααα≥
∂(21)/  a  \				∂(61)/  d  \
∂(21)\ ≤α≥ /				∂(61)\ ≤α≥ /
∂(21)≤'≥ ≤'≥				∂(61)≤`≥ ≤`≥
∂(20)/b ≤`≥ c\				∂(60)/e ≤'≥ f\
∂(20)`≥ `≥' ≤'				∂(60)`≥ `≤' ≤'
∂(22)`' `'				∂(62)`' `'
∂(29)T5i∂(34)T5ii∂(40)t3∂(44)T6i∂(49)T4∂(53)t6i	
∂(30)↔∂(35)↔∂(40)↔∂(45)↔∂(49)↔∂(54)↔
∂(24)  ≤≥a				∂(64)  ≤≥d
∂(21)+≤'  `≥+				∂(61)-≤'  `≥-
∂(21)/∂(21)≤αααααα≥∂(28)\		∂(61)/∂(61)≤αααααα≥∂(68)\
∂(20)b`αααααα'c				∂(60)e`αααααα'f
∂(24)+					∂(64)-


∂(38)Figure 3.
.apart
.end
	There are at least two different algorithms for determining the number
of strands in a knot using this graphic representation.  Many of the other
interesting questions about a knot such as can it be untangled (transformed
into a simple loop or point in the case of the graph) may not have known
decision procedures, but one could use the computer to check that a
series of transformations given as input have the intended effect.